#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// LCR 078. 合并 K 个升序链表
// https://leetcode.cn/problems/vvXgSW/description/

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution1
{
public:
    ListNode *mergeList(ListNode *lhs, ListNode *rhs)
    {
        ListNode *ret = nullptr;
        ListNode *ans = nullptr;
        while (lhs != nullptr && rhs != nullptr)
        {
            if (lhs->val < rhs->val)
            {

                ret = lhs;
                if (ans == nullptr)
                {
                    ans = ret;
                }
                ret = ret->next;
                lhs = lhs->next;
            }
            else
            {
                ret = rhs;
                if (ans == nullptr)
                {
                    ans = ret;
                }
                ret = ret->next;
                rhs = rhs->next;
            }
        }
        if (lhs == nullptr)
        {
            ret->next = rhs;
        }
        else
        {
            ret->next = lhs;
        }

        return ans;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        if (lists.size() < 1)
        {
            return lists[0];
        }
        ListNode *ans = nullptr;
        for (int i = 0; i + 1 < lists.size(); i++)
        {

            ans = mergeList(lists[i], lists[i + 1]);
            lists[i + 1] = ans;
        }
        return ans;
    }
};

class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
        ListNode *head = nullptr;
        ListNode *cur = nullptr;
        for (int i = 0; i < lists.size(); i++)
        {
            if (lists[i] != nullptr)
            {
                auto curPair = pair<int, int>(lists[i]->val, i);
                minHeap.push(curPair);
            }
        }
        while (!minHeap.empty())
        {
            int idex = minHeap.top().second;
            if (cur == nullptr)
            {
                cur = lists[idex];
                head = cur;
            }
            else
            {
                cur->next = lists[idex];
                cur = cur->next;
            }
            minHeap.pop();
            lists[idex] = lists[idex]->next;
            cur->next = nullptr;
            if (lists[idex] != nullptr)
            {
                minHeap.push(pair<int, int>(lists[idex]->val, idex));
            }
        }
        return head;
    }
};

int main()
{
    return 0;
}